package com.leetcodehot.problems;

import java.util.ArrayDeque;
import java.util.Deque;

public class problems2398 {
    public long sumOfRunning(int left, int right, int[] arr, long[] sum) {
        if (left == 0) {
            return sum[right];
        } else {
            return sum[right] - sum[left - 1];
        }
    }

    //max(chargeTimes) + k * sum(runningCosts)
    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        //down.getFirst()用来维持left与right之间最大值
        Deque<Integer> down = new ArrayDeque<>();
        int n = chargeTimes.length;
        long[] sumCosts = new long[n];
        int res = 0;
        //构建差分数组，用来快速返回sum
        sumCosts[0] = runningCosts[0];
        for (int i = 1; i < n; i++) {
            sumCosts[i] = sumCosts[i - 1] + runningCosts[i];
        }

        int left = 0;
        for (int i = 0; i < n; i++) {
            //当以机器人i为结尾的时候，包含i
            long x = chargeTimes[i];
            while (!down.isEmpty() && chargeTimes[down.getLast()] <= x) {
                //keep max
                down.removeLast();
            }
            down.addLast(i);
            //不符合条件left右进
            while (chargeTimes[down.getFirst()] + (i - left + 1) * sumOfRunning(left, i, runningCosts, sumCosts) > budget) {
                left++;
                //超过返回 去掉之前的最大值
                if (!down.isEmpty() && down.getFirst() < left) {
                    down.removeFirst();
                }
                if (down.isEmpty()) {
                    break;
                }
            }
            res = Math.max(res, i - left + 1);
        }
        return res;
    }
}
